package gold.contest;

import gold.utils.InputUtil;
import org.hamcrest.core.IsNull;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC2021_spring_contest_bytedance_01 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * ctm，原来是暴力法
     * @return:
     */
    class Solution {
        public int storeWater(int[] bucket, int[] vat) {
            int ans = Integer.MAX_VALUE;
            int maxPour = Integer.MIN_VALUE;
            for (int i = 0; i < vat.length; i++) {
                if (bucket[i] == 0) {
                    maxPour = Math.max(maxPour, vat[i]);
                } else {
                    maxPour = Math.max(maxPour, (int) Math.ceil((double) vat[i] / bucket[i]));
                }
            }
            if (maxPour == 0) {
                return 0;
            }
            //蓄水了j次
            for (int j = 1; j <= maxPour; j++) {
                int count = 0;
                for (int v = 0; v < vat.length; v++) {
                    int w = (int) Math.ceil((double) vat[v] / j);
                    if (w > bucket[v]) {
                        //比它小说明不用升级
                        count += (w - bucket[v]);
                    }
                }
                ans = Math.min(count + j, ans);
            }

            return ans;
        }
    }


    class Solution_Fail {
        public int storeWater(int[] bucket, int[] vat) {
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    double rate1 = o1[1] == 0 ? Integer.MAX_VALUE : 1.0 * o1[0] / o1[1];
                    double rate2 = o2[1] == 0 ? Integer.MAX_VALUE : 1.0 * o2[0] / o2[1];
                    return (rate1 - rate2) > 0.00000000001 ? -1 : 1;
                }
            });

            for (int i = 0; i < bucket.length; i++) {
                if (vat[i] <= 0) continue;
                priorityQueue.add(new int[]{bucket[i], vat[i]});
            }

            int minRatio = (int) (Math.ceil((1.0 * priorityQueue.peek()[1]) / (priorityQueue.peek()[0])));
            int count = 0;
            for (int[] pai : priorityQueue) {
                int curAdd = (int) (Math.ceil((1.0 * pai[1]) / (minRatio))) - pai[0];
                count += curAdd <= 0 ? 0 : curAdd;
            }
            return minRatio + count;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr1 = InputUtil.toIntegerArray("[9,0,1]");
        int[] arr2 = InputUtil.toIntegerArray("[0,2,2]");
        System.out.println(solution.storeWater(arr1, arr2));
    }

    public static void main(String[] args) throws Exception {
        LC2021_spring_contest_bytedance_01 an = new LC2021_spring_contest_bytedance_01();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
